package com.zhongge.code.sort;

import java.util.Arrays;

/**
 * @ClassName Insert
 * @Description TODO 插入排序
 * @Author zhongge
 * @Date 2025/10/3 21:33
 * @Version 1.0
 */
public class Insert {
    /**
     * 直接插入排序
     * @param arr 待排序数组
     */
    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if (tmp < arr[j]) {
                    arr[j+1] = arr[j];
                } else {//出现tmp>arr[j];
                    //优化：如果遇到比tmp大于前面的，
                    // 那么就直接退出了，因为根据直插的特点不会有比他大的了
                    break;
                }
            }
            //由于你j--是循环的最后执行语句所以最终落到了tmp空位之前
            //所以要将tmp加入到空位中必须得是j+1的位置
            arr[j+1] = tmp;
        }
    }

    public static void shellSort(int[] arr){
        //得到gap
        int gap = arr.length/2;
        while (gap >= 1) {
            //每一次进行希尔排序
            shell(arr, gap);
            gap/=2;
        }
    }

    /**
     * 希尔排序同族直插
     * @param arr 待排数组
     * @param gap 偏移量找同族
     */
    private static void shell(int[] arr, int gap){
        //每一组的希尔排序 同族使用直插 所以就只是偏移量的问题
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-gap;
            for (; j >= 0; j-=gap) {
                if (tmp < arr[j]) {
                    arr[j+gap] = arr[j];
                } else {
                    break;
                }
            }
            arr[j+gap] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5,4,3,2,1};
        System.out.println(Arrays.toString(arr));
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println("==================");
        int[] arr1 = {5,4,3,2,1};
        System.out.println(Arrays.toString(arr1));
        shellSort(arr1);
        System.out.println(Arrays.toString(arr1));
    }
}
